package mashibing.class20;

/**
 * 请同学们自行搜索或者想象一个象棋的棋盘，
 * 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
 * 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
 * 给你三个 参数 x，y，k
 * 返回“马”从(0,0)位置出发，必须走k步
 * 最后落在(x,y)上的方法数有多少种?
 */
public class Class20_2_HorseJump {

    private static int jump(int x, int y, int step) {
        return process(0, 0, step, x, y);
    }

    private static int process(int i, int j, int step, int x, int y) {
        if (i < 0 || i > 9 || j < 0 || j > 8) {
            return 0;
        }
        if (step == 0) {
            return (i == x && j == y) ? 1 : 0;
        }
        int way = process(i + 2, j + 1, step - 1, x, y);
        way += process(i + 1, j + 2, step - 1, x, y);
        way += process(i - 1, j + 2, step - 1, x, y);
        way += process(i - 2, j + 1, step - 1, x, y);
        way += process(i - 2, j - 1, step - 1, x, y);
        way += process(i - 1, j - 2, step - 1, x, y);
        way += process(i + 1, j - 2, step - 1, x, y);
        way += process(i + 2, j - 1, step - 1, x, y);
        return way;
    }

    private static int dp(int x, int y, int step) {
        int[][][] dp = new int[10][9][step + 1];
        dp[x][y][0] = 1;
        for (int k = 1; k <= step; k++) {
            for (int i = 0; i <= 9; i++) {
                for (int j = 0; j <= 8; j++) {
                    int way = pick(i + 2, j + 1, k - 1, dp);
                    way += pick(i + 1, j + 2, k - 1, dp);
                    way += pick(i - 1, j + 2, k - 1, dp);
                    way += pick(i - 2, j + 1, k - 1, dp);
                    way += pick(i - 2, j - 1, k - 1, dp);
                    way += pick(i - 1, j - 2, k - 1, dp);
                    way += pick(i + 1, j - 2, k - 1, dp);
                    way += pick(i + 2, j - 1, k - 1, dp);
                    dp[i][j][k] = way;
                }
            }
        }
        return dp[0][0][step];
    }

    private static int pick(int i, int j, int step, int[][][] dp) {
        if (i < 0 || i > 9 || j < 0 || j > 8) {
            return 0;
        }
        return dp[i][j][step];
    }

    public static void main(String[] args) {
        int x = 7;
        int y = 7;
        int step = 10;
        System.out.println(jump(x, y, step));       // 515813
        System.out.println(dp(x, y, step));
    }

}
